package com.lw.leetcode.arr.b;

import java.util.HashMap;
import java.util.Map;

/**
 * 1658. 将 x 减到 0 的最小操作数
 *
 * @Author liw
 * @Date 2021/6/12 14:54
 * @Version 1.0
 */
public class MinOperations {

    public static void main(String[] args){
        MinOperations test = new MinOperations();
//         nums = [3,2,20,1,1,3], x = 10
        int[] arr = {3,2,20,1,1,3};
        // nums = [5,6,7,8,9], x = 4
//        int[] arr = {5,6,7,8,9};
        // nums = [1,1,4,2,3], x = 5
//        int[] arr = {1,1,4,2,3};
        int i = test.minOperations(arr, 10);
        System.out.println(i);
    }

    public int minOperations(int[] nums, int x) {
        int length = nums.length;
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum < x) {
            return  -1;
        }
        if (sum == x) {
            return length;
        }
        int value = sum - x;
        int st = -1;
        int m = -1;
        int item = 0;
        for (int i = 0; i < length; i++) {
            item += nums[i];
            if (item == value) {
                m = Math.max(m, i - st);
            } else if (item > value) {
                while (item > value) {
                    item -= nums[++st];
                }
                if (item == value) {
                    m = Math.max(m, i - st);
                }
            }
        }
        return m == - 1 ? -1 : length - m;
    }

    public int minOperations2(int[] nums, int x) {
        int length = nums.length;
        Map<Integer, Integer> map = new HashMap<>(length << 1);
        int sum = 0;
        for(int i = length - 1; i >= 0; i--) {
            sum += nums[i];
            if (sum > x) {
                break;
            }
            map.put(sum, length - i);
        }
        map.put(0, 0);
        if (sum < x) {
            return -1;
        }
        long min = Long.MAX_VALUE;
        int value = 0;

        Integer c = map.get(x);
        if (c != null) {
            min = Math.min(c, min);
        }
        for (int i = 0; i < length; i++) {
            value += nums[i];
            if (value > x) {
                break;
            }
            c = map.get(x - value);
            if (c != null) {
                min = Math.min(c + i + 1, min);
                break;
            }
        }
        return min == Long.MAX_VALUE ? -1 : (int) min;
    }
}
